/**
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 */

/** 解题思路 **/

// 动态规划
// 此类求 多少种可能性 的题目一般都有 递推性质 ，即 f(n)和 f(n-1)…f(1) 之间是有联系的。
// 设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。
// 当为 1 级台阶： 剩 n-1个台阶，此情况共有 f(n-1)种跳法；
// 当为 2 级台阶： 剩 n-2个台阶，此情况共有 f(n−2) 种跳法。
// f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)

const f = (n) => {
  let [a, b, i] = [1, 1, 0];
  while (i < n) {
    [a, b] = [b, (a + b) % 1000000007];
    i++;
  }
  return a;
};

// 递归
const f2 = (n) => {
  if (n < 3) return n;
  return f(n - 1) + f(n - 2);
}

// 找规律
const f3 = (n) => {
  if (n < 3) return n;
  let [a, b] = [1, 2];
  for (let i = 3; i <= n; i++) {
    [b, a] = [(a + b) % 1000000007, b];
  }
  return b;
}

// 递归 缓存
const f4 = (n, arr = []) => {
  if (n < 3) return n;
  if (!!arr[n]) return arr[n];
  let a = f4(n - 1, arr);
  arr[n - 1] = a;
  let b = f4(n - 2, arr);
  arr[n - 2] = b;
  let res = (a + b) % 1000000007;
  arr[n] = res;
  return res;
}

const n = 1000
console.log(n, f(n), f2(n), f3(n), f4(n));